package week_02;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;

public class PermuteNums_46 {
    private List<List<Integer>> ans;
    private List<Integer> subset;
    private int n;
    private int[] nums;
    private boolean[] used;


    public List<List<Integer>> permute(int[] nums) {
        this.nums = nums;
        used = new boolean[n];
        for (int i = 0; i < n; i++) {
            used[i] = false;
        }
        //输入：nums = [1,2,3]
        //输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
        n = nums.length;
        ans = new ArrayList<>();
        subset = new ArrayList<>();
        int index = 0;
        dfs(index);
        return ans;
    }

    public void dfs(int index) {
        System.out.println(index);
        if (index == n + 1) {
            ans.add(new ArrayList<>(subset));
            return;
        }
        // 开始在n个位置占一个位置往下搜索
        for (int i = 0; i < n; i++) {
            // 如果遇上这个位置已经有占的了就continue
            //不加这个数
            if (used[i] == true) continue;
            used[i] = true;
            //加这个数
            subset.add(nums[index]);
            dfs(index + 1);
            subset.remove(subset.size() - 1);
            used[i] = false;
        }
    }

}
